2020SpringTraining

3.1 Schedule

Team:

每周日13:00-18:00 (网上/工训楼308) 训练

每个月抽出一次补题/讨论/总结

ZRX:

一周:

  1. 完成3个模板

  2. 除模板题外,4场CF 的 C到F,代码小于50行的且做法相同的可嘴。

  3. 如果打codeforces了 1和2的总量可以-1。

CJY:

每周:

3道 CF div1 C题以上的题

尽量 补完上次团队训练的题目

XX:

每周:

周一:一场CF(开VP)

周三:一个模板+两道典型题

周四:一个模板+两道典型题

周六:补训练赛题目

3.2 Training

3.2.1 ZRX

题目:

第0周:

CF 1285F 2800的题就是2800的题!利用莫比乌斯函数性质来求互质数个数!通过从大到小入栈,来保证最优答案不会被错过!太妙了!

第1周:

CF 1293F 我竟然能独立做出来一道2700的题哈哈哈哈哈哈哈哈哈哈哈哈,用了一点虚树的思想,树上只建关键点,想清再写!

CF 1268D 3100的题,真的是大开眼界…竞赛图,缩点之后类似链状的结构, 竞赛图强连通部分一定有n-1的环,还有简便判断是否为1个scc的方法

CF 1286F 3200的题,手滑了开了div1的F…DP思维真的很巧妙,把操作转换成了树上操作,然后奇数层偶数层分析得到结论,骚操作枚举子集复杂度还可以除二

第2周:

CF 1305D 比赛的时候没想出来,关注树的问题的时候多关注叶子有什么性质~

CF 1305F 比赛的时候没想出来,关于改变序列的值来改变gcd,一定要关注gcd=2啊,最优化的题,可以关注多数情况,然后随机化~

CF 1286D 挺不错的一个线段树,第一次碰撞只可能是相邻的两个之间发生!第i个事情发生的概率=前i个事情不发生的概率-前i-1个事情不发生的概率,所以按时间每次ban掉一个,

线段树维护dat[now][i][j]表示第now个节点,这个区间左边的向i方向,右边的向j方向。pushup的时候判断左边和右边的各4种情况,然后再判断区间能否合并即可。

第3周:

CF 1312F 比赛的时候想差不多了,打表找sg值规律好技能,sg值是后继的mex,本题是sg有循环节!

CF 1281F 挺不错的一道treedp吧,而且是处理连通块问题,熟悉一下树形dp写法,一个是外面要开temp,一个是循环完之后再加sz。

CF 1277F 没啥意思的一道题,倒是有点代码能力,从0开始的话写getpos(i,j) (m-1)*i 就不用-1了。

转移的时候,有合并两个连通块和不合并两种操作。因此似乎一般定义treedp状态,dp[i][j]是一个第i个点,第j个连通块还在接收新的点的状态。

第4周:

CF 1265F 关于括号序列层数的区间dp,可以删除无关括号,dp[l][r]表示l,r,区间的层数和,转移也很显然,就是莫名想不清正确性

CF 1255F 交互题,根据叉积的性质找凸包。先一直找更逆时针方向的直线,找出相邻的一个点,其他点根据面积从小到大排序,对于每个点与1构成的向量,再与比它高的点比较顺逆时针方向即可得到,连左或连右。

CF 1253F 很有趣的一道题,主要难在求k个点的最小生成树,可以用dijikstra,最开始bel [i in {k}]=i,跟着最短路更新bel,枚举每个边,如果两端的bel不同,那么给两端的bel连边,这样建图即可求最小生成树。

P.S.数组越界越多了似乎返回的是-1073741819。

第5周:

CF 1245F 自己做出来的一道2300的题。要求两个数都在[l,r]之间的数位dp。第一步肯定是容斥转换成每个数都是[0,x]之间的,ans=solve(r,r)-2*solve(l-1,r)+solve(l-1,l-1),之后两个数一起dp就好了。

CF 1247F 构造题,挺好的(想错做法,顺便出了一道新题)。显然每次可且最多可让深度+1,所以答案大小就确定了。每次合并到一条链上即可,只要让最长链最后合并即可,这题写法也很有趣。

CF 1244F 辣鸡模拟题,写吐了。

第6周:

CF 1244G 很常见的一种思路,先构造出最小的,每次变得最大的就是第i个和第n-i+1个交换,如果发现大了的话,显然可以在剩下的找到和多出来的相等的。

从Prufer编码到各种树的计数

从高斯消元到矩阵树定理

第7周:

从莫队到树上莫队

高精度模板整理

算法:

第0周:从线性筛到莫比乌斯反演

第1周:从哈密顿路到竞赛图(tournament)相关

CF比赛:

本学期开始:rating:1910

第2周 Ozon Tech Challenge 2020(div1+div2) rk753 rating:1956

第3周 Educational Codeforces Round 83 rk91 rating:2053

第6周 Codeforces Round 630(div 2) rk791 rating:2040

———————————————————训练调整分割线——————————————————

第8周 atcoder2 codeforces2 模板*1

第9周 atcoder2 codeforces1(比赛) 模板*1

团队比赛:

3.2.2 CJY

2020 CF rating: 2287

2020 Atcoder rating: 1779

补题:

BCPC 2020 F

2015-2016 Petrozavodsk Winter Training Camp, Moscow SU Trinity Contest B

3.2.3 XX

训练表

题目:

CF 1326 A B C D E(补题!!!)

CF 1323 A B C (补题!!!)

CF 1321 A B C D E F

CF 1313 A B C1 C2 D E

CF 1281 E F

CF 1271 E

比赛:

CF 1326

CF 1323

CF 1321

CF 1313

算法:

扩展KMP

CF rating:

2020.2.23 1776

2020.3.1 1788